package com.leetcode.algorithm.y19.m02;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.leetcode.algorithm.common.Employee;

/**
 * leetcode-cn.com
 * (done)463. 岛屿的周长
 * (done)594. 最长和谐子序列
 * (done)599. 两个列表的最小索引总和
 * (done)645. 错误的集合
 * (done)690. 员工的重要性
 * @author: jie.deng
 * @time: 2019年2月28日 上午10:39:48
 */
public class MySolution0228 {

	/**
	 * 463. 岛屿的周长
	 * 
	 * 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
	 * 
	 * 网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
	 * 
	 * 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100
	 * 。计算这个岛屿的周长。
	 * 
	 * 
	 * 
	 * 示例 :
	 * 
	 * 输入: [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]]
	 * 
	 * 输出: 16
	 * 
	 * 解释: 它的周长是下面图片中的 16 个黄色的边：
	 * 
	 * @param grid
	 * @return
	 */
	public int islandPerimeter(int[][] grid) {
		if (grid == null) {
			return 0;
		}
		int row = grid.length;
		if (row == 0) {
			return 0;
		}
		int col = grid[0].length;
		int sum = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (grid[i][j] == 1) {
					// 左边为0或者没有格子，周长加1
					if (j == 0 || grid[i][j - 1] == 0) {
						sum++;
					}
					// 右边为0或者没有格子，周长加1
					if (j == col - 1 || grid[i][j + 1] == 0) {
						sum++;
					}
					// 上边为0或者没有格子，周长加1
					if (i == 0 || grid[i - 1][j] == 0) {
						sum++;
					}
					// 下边为0或者没有格子，周长加1
					if (i == row - 1 || grid[i + 1][j] == 0) {
						sum++;
					}
				}
			}
		}
		return sum;
	}

	/**
	 * 594. 最长和谐子序列
	 * 
	 * 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
	 * 
	 * 现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,3,2,2,5,2,3,7] 输出: 5 原因: 最长的和谐数组是：[3,2,2,2,3]. 说明:
	 * 输入的数组长度最大不超过20,000.
	 * 
	 * @param nums
	 * @return
	 */
	public int findLHS(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}
		Map<Integer, Integer> numCntMap = new HashMap<Integer, Integer>();
		for (int num : nums) {
			numCntMap.put(num, numCntMap.get(num) == null ? 1 : 1 + numCntMap.get(num));
		}
		int max = 0;
		for (Integer num : numCntMap.keySet()) {
			Integer cnt = numCntMap.get(num);
			if (numCntMap.containsKey(num - 1) || numCntMap.containsKey(num + 1)) {
				int cntAround = Math.max(numCntMap.get(num - 1) == null ? 0 : numCntMap.get(num - 1),
						numCntMap.get(num + 1) == null ? 0 : numCntMap.get(num + 1));
				max = Math.max(max, cnt + cntAround);
			}
		}
		return max;
	}

	/**
	 * 599. 两个列表的最小索引总和
	 * 
	 * 假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
	 * 
	 * 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。
	 * 
	 * 示例 1:
	 * 
	 * 输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti",
	 * "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 输出:
	 * ["Shogun"] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。 示例 2:
	 * 
	 * 输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun",
	 * "Burger King"] 输出: ["Shogun"] 解释:
	 * 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。 提示:
	 * 
	 * 两个列表的长度范围都在 [1, 1000]内。 两个列表中的字符串的长度将在[1，30]的范围内。 下标从0开始，到列表的长度减1。
	 * 两个列表都没有重复的元素。
	 * 
	 * @param list1
	 * @param list2
	 * @return
	 */
	public String[] findRestaurant(String[] list1, String[] list2) {
		Map<String, Integer> strIdxMap = new HashMap<String, Integer>();
		for (int i = 0; i < list1.length; i++) {
			strIdxMap.put(list1[i], i);
		}
		List<String> list = new ArrayList<String>();
		int minIdxSum = list1.length + list2.length - 2;
		for (int i = 0; i < list2.length; i++) {
			if (strIdxMap.containsKey(list2[i])) {
				Integer idx = strIdxMap.get(list2[i]);
				if (idx + i < minIdxSum) {
					list.clear();
					list.add(list2[i]);
					minIdxSum = idx + i;
				} else if (idx + i == minIdxSum) {
					list.add(list2[i]);
				}
			}
		}
		return list.toArray(new String[0]);
	}

	/**
	 * 645. 错误的集合
	 * 
	 * 集合 S 包含从1到 n
	 * 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
	 * 
	 * 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
	 * 
	 * 示例 1:
	 * 
	 * 输入: nums = [1,2,2,4] 输出: [2,3] 注意:
	 * 
	 * 给定数组的长度范围是 [2, 10000]。 给定的数组是无序的。
	 * 
	 * @param nums
	 * @return
	 */
	public int[] findErrorNums(int[] nums) {
		int xor = 0;
		Set<Integer> set = new HashSet<Integer>();
		int repeat = 0;
		for (int num : nums) {
			xor ^= num;
			if (!set.add(num)) {
				repeat = num;
			}
		}
		for (int num = 1; num <= nums.length; num++) {
			xor ^= num;
		}
		return new int[] { repeat, repeat ^ xor };
	}

	/**
	 * 690. 员工的重要性
	 * 
	 * 给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。
	 * 
	 * 比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15,
	 * [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5,
	 * []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
	 * 
	 * 现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 输出: 11 解释:
	 * 员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。 注意:
	 * 
	 * 一个员工最多有一个直系领导，但是可以有多个直系下属 员工数量不超过2000。
	 * 
	 * @param employees
	 * @param id
	 * @return
	 */
	public int getImportance(List<Employee> employees, int id) {
		if (employees == null || employees.size() == 0) {
			return 0;
		}
		Map<Integer, Integer> importanceMap = new HashMap<Integer, Integer>();
		Map<Integer, Employee> empMap = new HashMap<Integer, Employee>();
		for (Employee emp : employees) {
			if (emp.subordinates == null || emp.subordinates.size() == 0) {
				// 当前员工没有直系下属
				if (emp.id == id) {
					return emp.importance;
				}
				importanceMap.put(emp.id, emp.importance);
			} else {
				empMap.put(emp.id, emp);
			}
		}
		return getImportance(id, importanceMap, empMap);
	}

	private int getImportance(int id, Map<Integer, Integer> importanceMap, Map<Integer, Employee> empMap) {
		if (importanceMap.containsKey(id)) {
			return importanceMap.get(id);
		} else {
			Employee emp = empMap.get(id);
			int importance = emp.importance;
			for (Integer empId : emp.subordinates) {
				importance += getImportance(empId, importanceMap, empMap);
			}
			importanceMap.put(id, importance);
			return importance;
		}
	}

}
